package com.feng.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author feng
 * @decrition
 * @date 2022/5/319:38
 */
public class L42 {
    public static void main(String[] args) {
//        int[] nums = {6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3};
//        int[] nums = {9,6,8,8,5,6,3};
        int[] nums = {2,8,5,5,6,1,7,4,5};
        int trap = trap(nums);
        System.out.println(trap);
    }

    public static int trap(int[] height) {
        List<Integer> list = new ArrayList<>();
        boolean flag = true;
        for (int i = 0; i < height.length - 1; i++) {
            if (height[i] > height[i+1] && flag) {
                list.add(i);
                flag = false;
            }
            if (height[i] <= height[i+1]) {
                if (i+1 == height.length - 1) {
                    list.add(i+1);
                }
                flag = true;
            }
        }
        if (list.size() < 2) {
            return 0;
        }
        int sum = 0;
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            Integer startIndex = list.get(i);
            int start = height[startIndex];
            int maxIndex = 0;
            int max = 0;
            for (int j = i+1; j < list.size(); j++) {
                Integer endIndex = list.get(j);
                int end = height[list.get(j)];
                if (start < end) {
                    for (int k = startIndex + 1; k < endIndex; k++) {
                        if (start > height[k]) {
                            int h = start - height[k];
                            sum += h;
                        }
                    }
                    i = j;
                    i--;
                    maxIndex = 0;
                    max = 0;
                    break;
                } else {
                    if (max <= end) {
                        max = end;
                        maxIndex = list.get(j);
                        i = j;
                        i--;
                    }
                }
            }
            if (maxIndex > i) {
                for (int j = startIndex + 1; j < maxIndex; j++) {
                    if (max > height[j]) {
                        int h = max - height[j];
                        sum += h;
                    }
                }
            }
        }

        return sum;
    }
}
